package com.le.medium.class4;


import org.junit.Test;

/**
 * 如果一个字符串为str，把字符串str前面任意的部分挪到后面形成的字符串叫 作str的旋转词。
 * 比如str="12345"，str的旋转词有"12345"、"23451"、 "34512"、"45123"和"51234"。
 * 给定两个字符串a和b，请判断a和b是否互为旋转 词。
 * 比如： a="cdab"，b="abcd"，返回true。 a="1ab2"，b="ab12"，返回false。 a="2ab1"，b="ab12"，返回true。
 */
public class Problem07_IsRotation {

    // 思路
    // 如果两者长度不一致，直接返回false
    // 长度一致，让a = a+a, a的子串必包含所有旋转词，使用kmp算法，判断b是否是a的子串
    // a = 12345, a+a = 1234512345, 任意长度为5的子串都是 旋转词
    public static boolean isRotation(String a, String b) {
        if (a == null || b == null || a.length() != b.length()) {
            return false;
        }
        String b2 = b + b;
        return getIndexOf(b2, a) != -1;
    }

    public static int getIndexOf(String a, String b) {
        char[] ss = a.toCharArray();
        char[] mm = b.toCharArray();
        int[] next = getNextArray(mm);
        int i = 0;
        int j = 0;
        while (i < ss.length && j < mm.length){
            if (ss[i] == mm[j]){
                i++;
                j++;
            }else if (next[j] == -1){
                i++;
            }else {
                j = next[j];
            }
        }
        return j == mm.length ? i - j : -1;
    }

    public static int[] getNextArray(char[] chs) {
        if (chs.length == 1) {
            return new int[]{-1};
        }
        int[] next = new int[chs.length];
        next[0] = -1;
        next[1] = 0;
        int i = 2;
        int cn = 0;
        while (i < chs.length) {
            if (chs[i - 1] == chs[cn]) {
                next[i++] = ++cn;
            }else if (cn > 0){
                cn = next[cn];
            }else {
                next[i++] = 0;
            }
        }
        return next;
    }

    @Test
    public void test(){
        String a = "12345";
        String b = "34512";
        System.out.println(isRotation(a,b));
    }
}
